package org.example.myleet.p659;

import java.util.*;

/**
 * 贪心算法
 * 哈希表的键为子序列的最后一个数字，值为最小堆，用于存储所有的子序列长度，最小堆满足堆顶的元素是最小的，因此堆顶的元素即为最小的子序列长度
 * 1、遍历数组，当遍历到元素 x 时，可以得到一个以 x 结尾的子序列。
 * 2、如果哈希表中存在以 x-1 结尾的子序列，则取出以 x-1 结尾的最小的子序列长度，将子序列长度加 1 之后作为以 x 结尾的子序列长度。此时，以 x−1 结尾的子序列减少了一个，以 x 结尾的子序列增加了一个。
 * 3、如果哈希表中不存在以 x−1 结尾的子序列，则新建一个长度为 1 的以 x 结尾的子序列。
 * 4、遍历结束时，遍历所有的子序列，如果存在不足长度为3的子序列，说明没有满足分割的办法
 */
public class Solution {
    public boolean isPossible(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        Map<Integer, List<SubSeq>> result = new HashMap<>();
        for (int x : nums) {
            //以x结尾的子序列
            SubSeq subSeq;
            if (result.containsKey(x-1)) {
                //存在x-1结尾的子序列，则将x追加到最短子序列，使之变成以x结尾的子序列
                List<SubSeq> subSeqs = result.get(x-1);
                subSeqs.get(0).seq.add(x);
                //此子序列的结尾便不是x-1，因此从x-1结尾的子序列中移除
                subSeq = subSeqs.remove(0);
                if (subSeqs.size() < 1) {
                    //没有x-1结尾的子序列，移除key
                    result.remove(x-1);
                }
            } else {
                //不存在x-1结尾的子序列，则新建以x结尾的子序列
                subSeq = new SubSeq(x);
            }
            if (result.containsKey(x)) {
                //存在x结尾的子序列，则新的subSeq添加到集合中，并进行长度升序排序
                List<SubSeq> subSeqs = result.get(x);
                subSeqs.add(subSeq);
                subSeqs.sort(Comparator.naturalOrder());
            } else {
                //不存在x结尾的子序列，则新建这个key
                List<SubSeq> newSubSeqList = new ArrayList<>();
                newSubSeqList.add(subSeq);
                result.put(x, newSubSeqList);
            }
        }
        for (List<SubSeq> subSeqs : result.values()) {
            for (SubSeq subSeq : subSeqs) {
                if (subSeq.seq.size() < 3) {
                    //存在不足长度为3的子序列，说明不存在分割方法，失败
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 子序列
     */
    static class SubSeq implements Comparable<SubSeq> {
        List<Integer> seq;

        public SubSeq(int num) {
            seq = new ArrayList<>();
            seq.add(num);
        }

        @Override
        public String toString() {
            return seq.toString();
        }

        @Override
        public int compareTo(SubSeq o) {
            //按照长度升序排列
            return this.seq.size() - o.seq.size();
        }
    }
}
